package com.interview.javabasic.Search;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class FinbonacciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,100,1234};
        System.out.println(fibSearch(arr,1234));
    }

    //需要使用斐波那契数列
    //用费递归的方式得到
    //mid = lowf(n-1)+1
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0]= 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i-1]+f[i-2];
        }
        return f;
    }

    //使用非递归的方式
    public static int fibSearch(int arr[] ,int key){
        int low = 0;
        int high = arr.length-1;
        int k = 0;//表示要分割的下标
        int mid = 0;
        int f[] =fib();
        //获取分割下标
        while (high>f[k] - 1){
            k++;
        }
        int[] tmp = Arrays.copyOf(arr,f[k]);
        //实际上需要使用数组的数据填充
        for (int i=high+1;i<tmp.length;i++){
            tmp[i]=arr[high];
        }
        //使用while循环处理
        while (low<=high){
            mid = low + f[k-1] - 1;
            if (key < tmp[mid]){
                high = mid -1;
                //为什么是key--，
                /*
                * f[k] = f[k-1]+f[k-2]
                * 因为前面有f[k-1]个元素，所以可以继续拆分
                * */
                k--;
            }else if (key >tmp[mid]){
                low = mid + 1;
                k -=2;
            }else{
                if (mid <=high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;

    }
}
